//https://www.lintcode.com/problem/integer-to-roman/description

// • 1~9: {"I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
// • 10~90: {"X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
// • 100~900: {"C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
// • 1000~3000: {"M", "MM", "MMM"}

// • 数位分离之后直接转换
// • 如何数位分离？ %10 /10
// • （扩展）如何将一个数转成k进制？ % k / k


class Solution {
public:
    /**
     * @param n: The integer
     * @return: Roman representation
     */
    string intToRoman(int n) {
        string result = "";
        string digits[4][9] = {{"I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},
                {"X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
                {"C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
                {"M", "MM", "MMM", "", "", "", "", "", ""}};
        int i = 0;
        while (n)
        {
            int tmp = n % 10;
            n = n / 10;
            if (tmp != 0)
            {
                result = digits[i][tmp - 1] + result;
            }
            i++;
        }
        return result;
    }
};